#include <iostream>

using namespace std;

int binary_search(int arr[], int size, int target) {
  int mid;
  int left = 0, right = size - 1;
  while (left != right) {
    mid = size / 2 + left;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      left = mid;
    }
    size = right - left + 1;
  }
  return -1;
}

namespace hashsearch {
enum Status { SUCCESS = 0, FAILED = 1 };
#define HASHSIZE 11
#define NULLKEY -INT16_MAX

typedef struct {
  int *elem;
  int cnt;
} HashTable;

int t_size = 0;

Status InitHashTable(HashTable *H) {
  t_size = HASHSIZE;
  H->cnt = t_size;
  H->elem = (int *)malloc(t_size * sizeof(int));
  for (int i = 0; i < t_size; ++i) {
    H->elem[i] = NULLKEY;
  }
  return Status::SUCCESS;
}

int HashFunc(int key) { return key % t_size; }

void InsertHash(HashTable *H, int key) {
  int addr = HashFunc(key);
  // 出现冲突
  while (H->elem[addr] != NULLKEY) {
    // 线性探测
    addr = (addr + 1) % t_size;
  }
  H->elem[addr] = key;
}

Status HashSearch(HashTable *H, int key, int *addr) {
  // 取哈希
  *addr = HashFunc(key);
  // 检测冲突
  while (H->elem[*addr] != key) {
    // 线性探测
    *addr = (*addr + 1) % t_size;
    // 往后找到空位或者已经找了一周了
    if (H->elem[*addr] == NULLKEY || *addr == HashFunc(key)) {
      *addr = -1;
      return Status::FAILED;
    }
  }
  return Status::SUCCESS;
}

int hash_search(HashTable *ht, int arr[], int size, int target) {
  int idx = -1;
  HashSearch(ht, target, &idx);
  return idx;
}

}  // namespace hashsearch

int seq_search(int arr[], int size, int target) {
  for (int i = 0; i < size; ++i) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

int main(int argc, char const *argv[]) {
  int A[10] = {4, 6, 12, 20, 28, 38, 50, 70, 88, 100};

  cout << seq_search(A, sizeof(A) / sizeof(int), 20) << endl;
  cout << binary_search(A, sizeof(A) / sizeof(int), 20) << endl;

  {
    using namespace hashsearch;
    HashTable ht;
    InitHashTable(&ht);
    for (int i = 0; i < 10; ++i) {
      InsertHash(&ht, A[i]);
    }
    // TODO: pair<key, idx>
    cout << hash_search(&ht, A, 10, 20) << endl;
    cout << hash_search(&ht, A, 10, 70) << endl;
    cout << hash_search(&ht, A, 10, 53) << endl;
  }

  return 0;
}
